package leetcode;


import java.util.HashMap;
import java.util.Map;

/**
 * 通过一个双向链表 + 散列表hashMap实现一个lru数据挤结构
 */

class LruCacheLinkedMap{

}

class LRUCache {

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(16);
        for (int i = 0; i < 20; i++) {
            lruCache.put(i, i);
        }

        System.out.println(lruCache);
    }

    // 定义一个双向链表
    static class Node {
        Integer key;
        Integer value;
        public Node(Integer key, Integer value) {
            this.key = key;
            this.value = value;
        }
        Node pre;
        Node next;
    }

    private int capitical = 0;
    private Map<Integer, Node> map;
    private Node head;
    private Node tail;

    public LRUCache(int cap){
        capitical = cap;
        map = new HashMap<>(capitical);
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        // 先删除该节点，再接到尾部
        node.pre.next = node.next;
        node.next.pre = node.pre;
        moveToTail(node, false);
        return node.value;
    }


    public void put(int key, int value) {
        // 直接调用这边的get方法，如果存在，它会在get内部被移动到尾巴，不用再移动一遍,直接修改值即可
        if (get(key) != -1) {
            map.get(key).value = value;
            return;
        }
        // 若不存在，new一个出来,如果超出容量，把头去掉
        Node node = new Node(key, value);
        map.put(key, node);
        moveToTail(node, true);

        if (map.size() > capitical) {
            map.remove(head.next.key);
            head.next = head.next.next;
            head.next.pre = head;
        }
    }

    /**
     * 几个操作
     * 1. put mapPut,
     * 2. get
     * 3. remove
     */

    private void moveToTail(Node node, boolean isInsert){
        if(!isInsert){
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        node.next = tail;
        node.pre = tail.pre;
        tail.pre = node;
        node.pre.next = node;
    }

}
